// https://leetcode.cn/problems/uncrossed-lines/description/

// 算法思路总结：
// 1. 使用动态规划求解不相交的连线最大数量
// 2. dp[i][j]表示nums1前i个元素和nums2前j个元素的最大连线数
// 3. 元素相等时连线数等于左上角值加1
// 4. 元素不等时取上方和左方的最大值
// 5. 本质是最长公共子序列问题的变形应用

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2)
    {
        int m = nums1.size(), n = nums2.size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 1 ; j <= n ; j++)
            {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
};

int main()
{
    vector<int> v11 = {1,4,2}, v12 = {1,2,4};
    vector<int> v21 = {2,5,1,2,5}, v22 = {10,5,2,1,5,2};

    Solution sol;

    cout << sol.maxUncrossedLines(v11, v12) << endl;
    cout << sol.maxUncrossedLines(v21, v22) << endl;

    return 0;
}